class Solution:
    def longestPrefix(self, s: str) -> str:
        '''
        Rabin-Karp 字符串编码
        参考官方题解
        https://leetcode.cn/problems/longest-happy-prefix/solution/zui-chang-kuai-le-qian-zhui-by-leetcode-solution/
        '''
        n = len(s)
        prefix, suffix = 0, 0
        base, mod, mul = 31, 1000000007, 1
        happy = 0
        for i in range(1, n):
            prefix = (prefix * base + (ord(s[i - 1]) - 97)) % mod
            suffix = (suffix + (ord(s[n - i]) - 97) * mul) % mod
            if prefix == suffix:
                happy = i
            mul = mul * base % mod
        return s[:happy]

    def longestPrefix2(self, s: str) -> str:
        '''
        KMP算法
        '''
        n = len(s)
        fail = [-1] * n
        for i in range(1, n):
            j = fail[i - 1]
            while j != -1 and s[j + 1] != s[i]:
                j = fail[j]
            if s[j + 1] == s[i]:
                fail[i] = j + 1

        return s[:fail[-1] + 1]

    def longestPrefix3(self, s: str) -> str:
      j, next = 0, [0] * len(s)
      for i in range(1, len(s)):
        while j > 0 and s[j] != s[i]:
          j = next[j - 1]
        if s[j] == s[i]:
          j += 1
        next[i] = j
      return s[:next[-1]]
    

